import random

def merge(lst):
    if len(lst) <= 1:
        return lst
    
    mid = len(lst)//2
    lst1 = merge(lst[:mid])
    lst2 = merge(lst[mid:])

    result =list()
    while lst1 and lst2:
        if lst1[-1]>lst2[-1]:
            result.append(lst1.pop())
        else:
            result.append(lst2.pop())
    result.extend(reversed(lst1 if lst1 else lst2))
    
    result.reverse()
    return result

if __name__ == "__main__":    
    n = 1000
    lst = list({random.randrange(n,10*n-1) for _ in range(n)})
    print(merge(lst)==sorted(lst))
    # print(merge(lst))